#include <iostream>
using namespace std;
#include <stack>
#include <vector>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

//class Solution {
//public:
//    ListNode* reverseBetween(ListNode* head, int left, int right) {
//        if (left == right)
//        {
//            return head;
//        }
//        int n = 1;
//        ListNode* n1 = head;
//        ListNode* n2 = nullptr;
//        ListNode* n3 = head;
//        ListNode* n4 = nullptr;
//        ListNode* newhead = head;
//        if (left == 1)
//        {
//            newhead = nullptr;
//        }
//        while (n1 != nullptr)
//        {
//            if (n >= left && n <= right)
//            {
//                if (n == left)
//                {
//                    n3 = n2;
//                    n4 = n1;
//                }
//                else if (n == right)
//                {
//                    if (newhead == nullptr)
//                    {
//                        n4->next = n1->next;
//                        newhead = n1;
//                    }
//                    else
//                    {
//                        n3->next = n1;
//                        n4->next = n1->next;
//                    }
//                }
//                ListNode* n5 = n1->next;
//                n1->next = n2;
//                n2 = n1;
//                n1 = n5;
//                n++;
//            }
//            else
//            {
//                n2 = n1;
//                n1 = n1->next;
//                n++;
//            }
//        }
//        return newhead;
//    }
//};

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* ll1 = l1;
        ListNode* ll2 = l2;
        ListNode* newhead = nullptr;
        ListNode* tail = nullptr;
        while (ll1 || ll2)
        {
            if (newhead == nullptr)
            {
                tail = newhead = new ListNode(0);
            }
            else if (tail->next != nullptr)
            {
                tail = tail->next;
            }
            else
            {
                tail->next = new ListNode(0);
                tail = tail->next;
                tail->next = nullptr;
            }
            if (ll1 == nullptr)
            {
                tail->val = tail->val + ll2->val;
                ll2 = ll2->next;
            }
            else if (ll2 == nullptr)
            {
                tail->val = tail->val + ll1->val;
                ll1 = ll1->next;
            }
            else
            {
                tail->val = tail->val + ll1->val + ll2->val;
                ll1 = ll1->next;
                ll2 = ll2->next;
            }
            if (tail->val > 9)
            {
                tail->next = new ListNode(1);
                tail->val %= 10;
                tail->next->next = nullptr;
            }
        }
        return newhead;
    }
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (!list1)
        {
            return list2;
        }
        else if (!list2)
        {
            return list1;
        }
        ListNode* newnode = list1->val < list2->val ? list1 : list2;
        ListNode* tail = newnode;
        while (list1 && list2)
        {
            if (list1->val < list2->val)
            {
                ListNode* l1 = list1->next;
                tail->next = list1;
                list1 = l1;
                tail = tail->next;
            }
            else
            {
                ListNode* l2 = list2->next;
                tail->next = list2;
                list2 = l2;
                tail = tail->next;
            }
        }
        if (list1)
        {
            tail->next = list1;
        }
        if (list2)
        {
            tail->next = list2;
        }
        return newnode;
    }
};

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr)
        {
            return nullptr;
        }
        Node* tail = head;
        while (tail)
        {
            Node* newnode = new Node(tail->val);
            newnode->next = tail->next;
            tail->next = newnode;
            tail = newnode->next;
        }
        tail = head;
        Node* nexttail = head->next;
        while (tail && nexttail)
        {
            if (tail->random == nullptr)
            {
                nexttail->random = nullptr;
            }
            else
            {
                nexttail->random = tail->random->next;
            }
            tail = nexttail->next;
            if (tail == nullptr)
            {
                break;
            }
            nexttail = tail->next;
        }
        tail = head;
        Node* newhead = head->next;
        nexttail = head->next;
        while (tail && nexttail)
        {
            tail->next = nexttail->next;
            tail = tail->next;
            if (tail == nullptr)
            {
                break;
            }
            nexttail->next = tail->next;
            nexttail = nexttail->next;
        }
        return newhead;
    }
};